package com.base.dp;

public class MaximalSquare {
    public static void main(String[] args) {
        MaximalSquare maximalSquare = new MaximalSquare();
        System.out.println(maximalSquare.maximalSquare(new char[][]{
                {'1', '0', '1', '0', '0'},
                {'1', '0', '1', '1','1'},
                {'1', '1', '1', '1','1'},
                {'1', '0', '0', '1','0'}
        }));

    }

    private int maximalSquare(char[][] chars) {
        if (chars == null || chars.length == 0) {
            return 0;
        }

        int m = chars.length;
        int n = chars[0].length;
        int[][] dp = new int[m][n];
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                //第一行或者第一列的处理方式
                if (i == 0 || j == 0) {
                    if (chars[i][j] == '1') {
                        dp[i][j] = 1;
                        max = Math.max(max, dp[i][j]);
                    }
                }else if (chars[i][j] == '1') {
                    dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                    max = Math.max(max, dp[i][j]);
                }
            }
        }
        return max*max;
    }
}
